/**
 * Created by sunchenglin on 2017/7/17.
 *希尔排序
 //    冒泡排序
 //    选择排序
 //    计数排序
 //    桶排序
 //    基数排序
 //    拓扑排序
 //    外部排序
 */
public class Solution {
    public static void change(int i, int j, int[] array){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

//往前找，比自己小的下移一位，比自己大的大的往后移动，然后插入。
    public static void shellSort(int[] array){
        int N = array.length;
        int h=1;
        while(h<N/3)h=3*h+1;
        while(h>=1){
            for(int i=h; i<N; i++){
                for(int j=i;j>=h && array[j]<array[j-h];j-=h){
                    change(j,j-h,array);
                }
            }
            h = h/3;
        }
    }
//插入排序，如果j比前面的小，交换位置。
    public static void insertSort(int[] array){
        int N = array.length;
        for(int i=1; i<N; i++){
            for(int j=i;j>=0 && array[j]<array[j-1];j--){
                change(j,j-1,array);
            }
        }
    }

    public static void main(String args[]){
        int[] a={7,4,8,5,3,4,5,2,6};
        shellSort(a);
        System.out.println("haha");
    }
}
